package com.suanfa.node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 填充二叉树的next指针，指向下一个节点
 */
public class NodeFillNext {


    public static Node connect(Node head){

        if(head == null){
            return null;
        }

        if(head.left != null){
            if (head.right != null){
                head.left.next = head.right;
            }else {
                head.left.next = getNext(head.next);
            }
        }

        if(head.right != null){
            head.right.next = getNext(head.next);
        }

        // 先确保 root.right 下的节点的已完全连接，因 root.left 下的节点的连接
        // 需要 root.left.next 下的节点的信息，若 root.right 下的节点未完全连
        // 接（即先对 root.left 递归），则 root.left.next 下的信息链不完整，将
        // 返回错误的信息。可能出现的错误情况如下图所示。此时，底层最左边节点将无
        // 法获得正确的 next 信息：
        //                  o root
        //                 / \
        //     root.left  o —— o  root.right
        //               /    / \
        //              o —— o   o
        //             /        / \
        //            o        o   o

        connect(head.right);
        connect(head.left);
        return head;
    }

    public static Node getNext(Node node){
        while (node != null) {
            if (node.left != null) {
                return node.left;
            }
            if (node.right != null) {
                return node.right;
            }
            node = node.next;
        }
        return null;
    }


    public static Node queueFile(Node head) {
        Queue<Node> node = new LinkedList<>();
        node.add(head);
        Node current = head;
        if (!node.isEmpty()) {
            int count = node.size();
            Node pre = null;
            for (int i = 0; i < count; i++) {
                Node n = node.poll();
                if (pre != null) {
                    pre.next = n;
                }
                pre = n;
                if (n.left != null) {
                    node.add(n.left);
                }
                if (n.right != null) {
                    node.add(n.right);
                }
            }

        }
        return head;
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    ;
}


